package org.basis.algorithm.list;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.SingleNode;

/**
 * 打印链表公共部分
 * 【题目】 给定两个【 有序链表 】的头指针head1和head2，打印两个链表的公共部分。
 * 【要求】 如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复 杂度要求为O(1)
 *
 * @author Mr_wenpan@163.com 2021/12/08 21:51
 */
public class PrintListCommonPart {

    public static void main(String[] args) {
        SingleNode<Integer> head1 = ListNodeUtil.generateIntegerSingleList(40, 80, true);
        SingleNode<Integer> head2 = ListNodeUtil.generateIntegerSingleList(40, 80, true);
        ListNodeUtil.printSingleList(head1);
        ListNodeUtil.printSingleList(head2);
        printCommon(head1, head2);
    }

    public static void printCommon(SingleNode<Integer> head1, SingleNode<Integer> head2) {
        if (head1 == null || head2 == null) {
            return;
        }
        // 从两个链表头开始走，相等就打印，谁小谁往前走
        while (head1 != null && head2 != null) {
            if (head1.data.equals(head2.data)) {
                System.out.print(head1.data + "   ");
                head1 = head1.next;
                head2 = head2.next;
            } else if (head1.data > head2.data) {
                head2 = head2.next;
            } else {
                head1 = head1.next;
            }
        }

    }


}
